import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/9/15 上午 10:17
 */
public class day190915 {

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        while (i >= 0 && nums[i + 1] <= nums[i]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        reverse(nums, i + 1);
    }

    private void reverse(int[] nums, int start) {
        int i = start, j = nums.length - 1;
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int maxNumberOfBalloons(String text) {
        int[] charMap = new int[26];
        char[] chars = text.toCharArray();
        for (char aChar : chars) {
            charMap[aChar - 'a'] ++;
        }
        int cnt = 0;
        while (charMap[0] > 0) {
            if (charMap['b' - 'a'] > 0) {
                charMap['b' - 'a'] --;
            } else {
                break;
            }
            if (charMap['l' - 'a'] > 1) {
                charMap['l' - 'a'] -= 2;
            } else {
                break;
            }
            if (charMap['o' - 'a'] > 1) {
                charMap['o' - 'a'] -= 2;
            } else {
                break;
            }
            if (charMap['n' - 'a'] > 0) {
                charMap['n' - 'a'] --;
            } else {
                break;
            }
            charMap[0] --;
            cnt++;
        }
        return cnt;
    }

    public String reverseParentheses(String s) {
        if (s.length() <= 1) {
            return s;
        }
        if (!s.contains("(")) {
            return s;
        }
        List<Character> temp = new ArrayList<>();
        Stack<Character> alphas = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (aChar >= 'a' && aChar <= 'z') {
                alphas.add(aChar);
            } else if (aChar == ')'){
                temp = new ArrayList<>();
                while (alphas.peek() != '(') {
                    temp.add(alphas.pop());
                }
                alphas.pop();
                alphas.addAll(temp);
            } else {
                alphas.add(aChar);
            }
        }
        StringBuilder builder = new StringBuilder();
        while (!alphas.isEmpty()) {
            builder.append(alphas.pop());
        }
        return builder.reverse().toString();
    }

    public static void main(String[] args) {
        day190915 day190915 = new day190915();
        System.out.println(day190915.reverseParentheses("ta()usw((((a))))"));
    }

    public int kConcatenationMaxSum(int[] arr, int k) {
        boolean allPositive = true;
        boolean allNegative = true;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= 0) {
                allNegative = false;
            }
            if (arr[i] < 0) {
                allPositive = false;
            }
        }
        if (allNegative) {
            return 0;
        }
        if (allPositive) {
            int sum = 0;
            for (int i : arr) {
                sum += i % 1000000007;
            }
            return (sum * k) % 1000000007;
        }
        return 0;
    }
}
